\documentclass[12pt,a4paper]{article}
\usepackage{xeCJK}
\usepackage{ctex}
\usepackage{booktabs}
\usepackage{makecell}
\usepackage{geometry}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{graphicx}
\usepackage{wrapfig}
\usepackage{abstract}
\usepackage{float}
\usepackage{algorithmicx}
\usepackage[ruled]{algorithm}
\usepackage{algpseudocode}
\usepackage{xcolor}
\usepackage{setspace}
\usepackage{color}
\usepackage{bm}
\usepackage{url}
\usepackage{cite}
\usepackage{array}
\usepackage{textcomp}
\usepackage{appendix}
\usepackage{latexsym}%约等号\approx
\usepackage{listings}
\usepackage{amsfonts}%有双竖线的大写字母宏包 \mathbb{}
\usepackage{mathrsfs}%花写体宏包 \mathscr{}

\definecolor{dkgreen}{rgb}{0,0.6,0}
\definecolor{gray}{rgb}{0.5,0.5,0.5}
\definecolor{mauve}{rgb}{0.58,0,0.82}
\lstset{frame=tb,
  language=Python,
  aboveskip=3mm,
  belowskip=3mm,
  showstringspaces=false,
  columns=flexible,
  basicstyle={\small\ttfamily},
  numbers=left,%设置行号位置none不显示行号
  %numberstyle=\tiny\courier, %设置行号大小
  numberstyle=\tiny\color{gray},
  keywordstyle=\color{blue},
  commentstyle=\color{dkgreen},
  stringstyle=\color{mauve},
  breaklines=true,
  breakatwhitespace=true,
  escapeinside=``,%逃逸字符(1左面的键)，用于显示中文例如在代码中`中文...`
  tabsize=4,
  extendedchars=false %解决代码跨页时，章节标题，页眉等汉字不显示的问题
}

\lstset{language=C}

\lstset{
    %numbers=left, 
    %numberstyle= \tiny, 
    keywordstyle= \color{ blue!70},
    commentstyle= \color{red!50!green!50!blue!50}, 
    frame=shadowbox, % 阴影效果
    rulesepcolor= \color{ red!20!green!20!blue!20} ,
    escapeinside=``, % 英文分号中可写入中文
    xleftmargin=2em, aboveskip=1em,
    framexleftmargin=2em
}

\setstretch{1.2} 
\setlength{\parindent}{0.8cm}
\geometry{left=3cm,right=3cm,top=2.5cm,bottom=2.5cm}
\title{\vspace{-2cm} \textbf{Project Report}}

\author{赵竟廷 3200105665}
\date{December 2022}

\begin{document}
\maketitle

\section{项目简介及运行说明}

根据该项目的总体要求，本次项目中主要包含以下几部分程序，分别是：
\textcircled{1}头文件spline.h（包含通过ppForm和Bspline实现相应样条功能以及函数、曲线拟合的算法）
\textcircled{2}测试文件（通过解决3.6.2中的题目完成对所有功能的测试，分为：proA.cpp、proCD.cpp、proE.cpp）
\textcircled{3}输入文件（使用json file实现参数的输入）。
\textcircled{4}Makefile文件（实现程序的统一管理）。

编译时，只需终端输入“make”即可编译所有程序。

分别输入“./testA”、“./testCD”、 “./testE”可以分别运行proA.cpp、proCD.cpp、proE.cpp。

\section{程序设计思路}

\begin{itemize}
    \item \textbf{头文件 spline.h}

    首先定义一个多项式类\textbf{PiecewisePoly}，用于储存分段多项式。具体地，利用其成员变量begin和end来储存每一段的起始和终止插值点，利用coe来储存每一段多项式的各次项前系数，exp来储存该系数所对应的x的次数，即coe[0]储存exp[0]次项前系数，其他同理。

    其次定义一个求解基类\textbf{Solve\_Base}。这是由于本题ppForm与Bspline在求解的目的上是一样的，均希望输入插值点及其函数值以及插值点个数来求得类别是PiecewisePoly类的解。其中插值点及其对应的函数值分别通过向量$_x$和向量$_y$输入。此处并没有规定求解基类是一个虚类，主要原因是在具体实现的过程中后续的类中的函数可能会与此处规定的成员函数或成员变量有一定的出入。因此为保证程序的顺利进行和灵活性，此处没有设计为虚类。

    \textbf{class ppForm}是一个可以通过ppForm方法实现样条插值的类，它继承求解基类Solve\_Base。该类中有两个成员函数S\_01()和S\_23(int,double,double)，分别用于求解线性插值样条和三次样条。其中S\_01()无需参数输入，而S\_23则需要用户输入三个参数。由于三次样条有三种不同的情况，因此将三次样条的第一个输入参数作为条件参数。相应地，输入条件参数为1表示求解的是完全样条、参数为2表示D2样条、参数为3表示自然样条。第二第三需要输入的参数则表示两个边界条件，当需要求解完全样条时，则输入插值总区间左端点及右端点的一阶导数值；当需要求解D2样条时，则输入插值总区间左端点及右端点的二阶导数值。规定在自然样条的情况下后两个参数只能输入0，若输入其他值系统将给出报错提醒，并结束程序。具体的求解过程参考课本Section 3.1中知识点设计。

    \textbf{class Bspline}是一个可以通过B样条递归方法实现样条插值的类，它继承求解基类Solve\_Base。该类中有三个成员函数S\_01()、S\_23(int,double,double)和S\_12(double,double)，分别用于求解线性插值样条、三次样条和二次样条。
    这里线性样条和三次样条的具体参数输入规则与ppForm类一致。需要说明的是，由于课本3.6.2题目需要，因此增加了求解二次样条的函数，该函数需要输入两个参数，分别是差值区间的左右整数端点的函数值。

    \textbf{class Curve}是一个用于曲线拟合的类。由于该类同样需要输入插值点个数及所有插值点且需要输出分段多项式类型的结果，因此也将其继承在了求解基类下。具体的算法实现方法参照课本定义3.71。该曲线拟合有三个结果值可以进行访问，其中answer对应所求得的x关于t的分段多项式，而answer\_则对应所求得的y关于t的分段多项式，t即为所求得的插值节点t。

    \item \textbf{测试文件}

    测试文件主要包含实现3.6.2中A、C、D、E题的程序proA.cpp、proCD.cpp、proE.cpp。

    proA.cpp中通过题目A测试了ppForm方法进行线性插值以及进行三种类型三次插值的算法可行性及正确性。

    proCD.cpp中通过题目C、D测试了Bspline方法进行线性插值、三种类型三次插值以及二次插值的算法可行性及正确性。

    proE.cpp通过题目E测试了曲线拟合算法的可行性和准确性。

    具体的测试结果将在下文叙述。

    \item \textbf{输入文件}

    项目在proA.cpp和proCD.cpp中使用了json file进行参数输入。其相应的文件分别是A.json和CD.json。需要说明的是，由于我在安装jsoncpp的时候出现了一些问题，最后我是在另一台电脑安装成功后将所需要的jsoncpp相应的文件下载到虚拟机内实现的json输入功能。因此，我在我的测试文件中也是直接include的json的头文件和cpp文件。为防止老师在编译的过程中出现问题，我已经将相应需要的jsoncpp的相关文件也上传在了项目作业文件夹中。老师只需将项目作业整个文件夹下载下来，再在文件夹中编译应该不会有问题。

    \item \textbf{输入报错提醒}

    根据上述叙述，在运行程序的过程中需要用户输入相应的参数，对于插值点个数、插值点及插值点函数值对应关系，以及条件参数、边界参数的输入都设置了报错提醒，如果用户输入的参数不符合规范，系统将会终止程序的运行并报错提示。
    
    \end{itemize}

\section{题目求解}
\subsection{Problem A}
本题中我分别通过完全三次样、D2三次样条、三次自然样条以及线性样条对不同个数的插值点来拟合函数$f(x)=\frac{1}{1+25x^2}$，并考察其各插值区间中点误差所形成的误差向量的无穷范数。其中使用A.json实现对插值点个数N的输入。
\subsubsection{输出文件}

统一编译结束，输入./testA运行后，将生成输出文件proA.txt。该文件中存有N为不同值时不同样条的误差向量的无穷范数值，以及用于绘制图像的数据点函数值。

\subsubsection{测试结果}

\begin{itemize}
    \item \textbf{误差情况}

    由于三次样条中完全样条、D2样条与自然样条的误差值较为接近，因此此处仅展示完全三次样条及线性样条的误差情况，具体的结果可以在输出文件中查看。

\begin{lstlisting}
---S_23 D1样条---
N = 6 ： maxnorm of error : 0.421705
N = 11 ： maxnorm of error : 0.0205289
N = 21 ： maxnorm of error : 0.00316894
N = 41 ： maxnorm of error : 0.000275356
N = 81 ： maxnorm of error : 1.609e-05

---S_01 样条---
N = 6 ： maxnorm of error : 0.5
N = 11 ： maxnorm of error : 0.05
N = 21 ： maxnorm of error : 0.0411765
N = 41 ： maxnorm of error : 0.0140271
N = 81 ： maxnorm of error : 0.00380126
\end{lstlisting}

\item \textbf{拟合图像}

根据输出文件中的图像点坐标利用matlab绘制相应拟合函数图像如下。

\begin{minipage}[t]{0.5\linewidth}
    \begin{figure}[H]
    \centering
    \includegraphics[height=4cm,width=5.3cm]{proA_D1.png}
    \caption{完全三次样条}
    \end{figure}
    \end{minipage}
    \begin{minipage}[t]{0.5\linewidth}
    \begin{figure}[H]
    \centering
    \includegraphics[height=4cm,width=5.3cm]{proA_D2.png}
    \caption{D2三次样条}
    \end{figure}
    \end{minipage}

    \begin{minipage}[t]{0.5\linewidth}
    \begin{figure}[H]
    \centering
    \includegraphics[height=4cm,width=5.3cm]{proA_na.png}
    \caption{三次自然样条}
    \end{figure}
    \end{minipage}
    \begin{minipage}[t]{0.5\linewidth}
    \begin{figure}[H]
    \centering
    \includegraphics[height=4cm,width=5.3cm]{proA_Line.png}
    \caption{线性样条}
    \end{figure}
    \end{minipage}
\end{itemize}

\subsubsection{结果分析}

\begin{itemize}
    \item \textbf{拟合情况分析}

根据误差结果以及上述拟合图像可知，三次样条的拟合效果要优于线性样条。分析可知线性样条在插值点处缺少光滑性，因此无法像光滑的三次样条一样达到较优的拟合效果。而三种类型的三次样条的拟合效果只有极小的差别，这一点在图像上也可以清晰的看出。当插值点个数较少时，相对而言完全三次样条的误差最小，自然样条的误差最大。而当插值点个数增加后，三种三次样条的误差在可视的小数位数内是一致的。

不仅如此，随着插值点数量的增加，样条的拟合效果越来越好，从图像上可以看到，当N=11时所得到的样条已经十分接近原函数。通过图像也可以看到，样条能够较好的避免Runge现象，能够在相对较少的插值点个数下达到较为精确的拟合目的。

\item \textbf{收敛阶分析}

由于插值点个数N=6，11，21，41，81可以近似看成以2为倍数的增长（即后一次的插值点个数近似于前一次的2倍），因此考虑以2的次数关系来分析误差随插值点个数的收敛情况。

针对三次样条，由于三种样条的误差值接近，因此仅用完全三次样条进行分析。
\begin{table}[H]
\renewcommand{\arraystretch}{1.2}
 \centering
 \label{tab:pagenum}
 \setlength{\tabcolsep}{0.8cm}{

 \begin{tabular}{ccccc}
  \toprule
  \multicolumn{1}{c}{\textbf{样条}}& \multicolumn{1}{c}{\textbf{比值1}}&
  \multicolumn{1}{c}{\textbf{比值2}}&
  \multicolumn{1}{c}{\textbf{比值3}}&
  \multicolumn{1}{c}{\textbf{比值4}}
  \\
  \midrule

\multicolumn{1}{c}{三次样条} & \multicolumn{1}{c}{$20.5420$} & \multicolumn{1}{c}{$6.4781$} & \multicolumn{1}{c}{$11.5085$} &  \multicolumn{1}{c}{$17.1134$}\\

\multicolumn{1}{c}{线性样条} & \multicolumn{1}{c}{$10$} & \multicolumn{1}{c}{$1.2142$} & \multicolumn{1}{c}{$2.9354$} &  \multicolumn{1}{c}{$3.6901$}\\
  \bottomrule
 \end{tabular}}
\end{table}

注：记N=6，11，21，41，81时的误差分别为误差1～5，表中比值i即为误差i与误差i+1的比值。

可以看到，随着插值点个数以2为倍数增加，三次样条拟合误差的缩小倍数越来越接近$2^4$，而线性样条拟合误差的缩小倍数越来越接近$2^2$。

因此三次样条的收敛阶约为4而线性样条的收敛阶约为2。

\end{itemize}

\subsection{Problem B}

根据题目要求，基于定理3.57和3.58的B-样条插值方法已在头文件spline.h中实现，具体的使用方法及参数输入与上文中提到的一致，此处不再赘述。

\subsection{Problem C}
本题利用定理3.57和3.58相关知识分别用完全三次B样条、D2三次B样条、三次自然B样条、二次B样条和线性B样条来拟合函数$f(x)=\frac{1}{1+x^2}$。

\subsubsection{输出文件}

统一编译结束，输入./testCD运行后，将生成输出文件proC.txt。该文件中存有用于绘制不同B样条拟合图像的数据点。

\subsubsection{拟合图像}

根据输出文件中的图像点坐标利用matlab绘制相应拟合函数图像如下。


    \begin{figure}[H]
    \centering
    \includegraphics[height=5cm,width=6.3cm]{proC.png}
    \caption{B样条拟合图像}
    \end{figure}

    从图像中可以初步看到三次样条的拟合效果最好且三种三次样条的拟合效果较为接近，而二次样条和线性样条拟合效果较差。具体的误差分析将在Problem D中详细叙述。

\subsection{Problem D}
本题使用CD.json文件实现7个带计算误差点的输入。本题承接上题，对上一题中的拟合误差做进一步分析。

\subsubsection{输出文件}

统一编译结束，输入./testCD运行后，将生成输出文件proD.txt。该文件中存有三次B样条、二次B样条、线性B样条在七个指定点-3.5,-3,-0.5,0,0.5,3,3.5处的误差，以及用于绘制不同B样条拟合误差图像的数据点。

\subsubsection{测试结果}

\begin{itemize}
    \item \textbf{误差值}


\begin{lstlisting}
-----cubic Bspline D1-----
0.000669568 1.11022e-16 0.0205289 2.84217e-14 0.0205289 8.02136e-15 0.000669568 

-----cubic Bspline D2-----
0.00068675 1.11022e-16 0.0205291 2.84217e-14 0.0205291 2.12885e-14 0.00068675 

-----cubic Bspline natural-----
0.000789971 4.16334e-16 0.0205306 2.13163e-14 0.0205306 3.06144e-14 0.000789971 

-----quadratic Bspline-----
4.16334e-17 0.00141838 1.11022e-16 0.120238 3.44169e-15 0.00141838 1.38778e-17 

-----linear Bspline-----
0.00394007 1.38778e-17 0.05 0 0.05 2.77556e-17 0.00394007 
\end{lstlisting}

其中每一组数据从左到右即依次对应点-3.5,-3,-0.5,0,0.5,3,3.5处的误差。

\item \textbf{误差图像}

\begin{minipage}[t]{0.5\linewidth}
    \begin{figure}[H]
    \centering
    \includegraphics[height=4cm,width=5.3cm]{proD_1.png}
    \caption{$S_1^0,S_2^1,S_3^2$ B样条误差}
    \end{figure}
    \end{minipage}
    \begin{minipage}[t]{0.5\linewidth}
    \begin{figure}[H]
    \centering
    \includegraphics[height=4cm,width=5.3cm]{proD_2.png}
    \caption{三种三次B样条误差}
    \end{figure}
    \end{minipage}

\end{itemize}

\subsubsection{结果分析}

首先根据误差图像可以明显看到，拟合准确度的排序是：三次样条>二次样条>线性样条。同时可以看到三种样条的误差均在大体上呈现中间大，两边小的趋势。同时二次样条在0点处的误差较大，这可能是由于二次B样条插值节点选取的特殊性造成的。由于二次B样条在选取插值节点的时候选择的并非整数点，因此无法精确体现在0这一极大值点的函数特征，因而在拟合时会呈现较大误差。而三种三次样条在靠近插值区间左右端点附近差别相对较大，而在0附近的误差几乎一致。对比而言，误差最小的仍然是完全三次样条，因此最精确的是完全三次B样条。

注意到其中有部分误差值的大小接近机器精度或为0，这些点均在插值节点的位置。由于我们利用插值点的准确函数值进行拟合，因此在这些点处的误差理论上应该为0。而这些点处没有等于0的原因可能是在进行线性方程计算或其他计算过程中产生了舍入误差，从而导致这样的结果。

\subsection{Problem E}

本题与前面的样条拟合与所不同。该题要求完成绘制的是一个闭合曲线，因此对于N个插值节点则要生成N个插值区间和分段多项式。由于曲线拟合中x和y关于t的导数并不易求得，且需要是一个连贯的闭环光滑图形，因此考虑用三次自然样条进行拟合以达到最佳效果。

同时需要注意的是，本题在选取插值点的过程中要沿着图像周线依次选取，否则将出现穿插绘制的情况，并不能构成一个封闭图形。本题选取$(0,\frac{2}{3}\sqrt{3})$作为起始点和截止点并从起始点开始按顺时针依次取相应个数的插值点。

\subsubsection{输出文件}

统一编译结束，输入./testE运行后，将生成输出文件proE.txt。该文件中存有N=10，40，160的情况下用于绘图的数据点坐标。

\subsubsection{绘制图像}

\begin{figure}[H]
    \centering
    \includegraphics[height=5cm,width=6.3cm]{proE.png}
    \caption{心形线绘制}
    \end{figure}

\subsubsection{结果分析}

通过图像观察可以发现随着插值点个数的增加曲线拟合效果越来越好，越来越接近心形线本来的样子。当N=40时所形成的形状已经较为接近原函数的样子，同时通过分析可以看出，插值点增长倍数是4，分析收敛阶的情况可知，该函数具有较强的收敛性质。

















\end{document}
